//130. 被围绕的区域




/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {
    let row = board.length
    if(row===0) return board
    let col = board[0].length

    class Pos{
        constructor(x,y){
            this.x =x
            this.y=y
        }
    }


    let que = []
    //第0行
    for(let i =0;i<col;i++){
        if(board[0][i]==='O'){
            let p = new Pos(0,i)
            que.push(p)
            board[0][i]='-'
        }
    }
    //最后一行
    for(let i =0;i<col;i++){
        if(board[row-1][i]==='O'){
            let p = new Pos(row-1,i)
            que.push(p)
            board[row-1][i]='-'
        }
    }
    //第一列 
    for(let j=1;j<row-1;j++){
        if(board[j][0]==='O'){
            let p = new Pos(j,0)
            que.push(p)
            board[j][0]='-'
        }
    }
    //最后一列
    for(let j=1;j<row-1;j++){
        if(board[j][col-1]==='O'){
            let p = new Pos(j,col-1)
            que.push(p)
            board[j][col-1]='-'
        }
    }
    while(que.length!==0){
        let {x,y} = que.pop()
        if(x!=0&&board[x-1][y]==='O'){
            board[x-1][y]='-'
            let p = new Pos(x-1,y)
            que.push(p)
        }
        if(x!=row-1&&board[x+1][y]==='O'){
            board[x+1][y]='-'
            let p = new Pos(x+1,y)
            que.push(p)

        }if(y!=0&&board[x][y-1]==='O'){
            board[x][y-1]='-'
            let p = new Pos(x,y-1)
            que.push(p)

        }if(y!=col-1&&board[x][y+1]==='O'){
            board[x][y+1]='-'
            let p = new Pos(x,y+1)
            que.push(p)
        }
    }
    for(let i=0;i<row;i++){
        for(let j=0;j<col;j++){
            if(board[i][j]==='O')board[i][j]='X'
            else if(board[i][j]==='-') board[i][j]='O'
        }
    }
};